package com.zs.letcode.top_interview_questions;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 多数元素
 * 给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于⌊ n/2 ⌋的元素。
 * <p>
 * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
 * <p>
 * 示例1：
 * <p>
 * 输入：[3,2,3]
 * 输出：3
 * 示例2：
 * <p>
 * 输入：[2,2,1,1,1,2,2]
 * 输出：2
 * <p>
 * 进阶：
 * <p>
 * 尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
 * 相关标签
 * 位运算
 * 数组
 * 分治算法
 * <p>
 * 作者：力扣 (LeetCode)
 * 链接：https://leetcode-cn.com/leetbook/read/top-interview-questions/xm77tm/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 *
 * @author madison
 * @description
 * @date 2021/5/22 17:16
 */
public class Chapter2 {
    public static void main(String[] args) {

    }

    private static class Solution {
        /**
         * 1，先排序
         * 给定的数组总是存在多数元素。也就是说肯定有一个元素的个数大于数组长度的一半。
         * 我们只需要把这个数组排序，那么数组中间的值肯定是存在最多的元素。
         */
        public int majorityElement(int[] nums) {
            Arrays.sort(nums);
            return nums[nums.length / 2];
        }

        /**
         * 2，使用Map解决
         */
        public int majorityElement1(int[] nums) {
            Map<Integer, Integer> counts = new HashMap<>();
            int length = nums.length;
            for (int i = 0; i < length; i++) {
                int count = counts.getOrDefault(nums[i], 0) + 1;
                if (count > length / 2) {
                    return nums[i];
                }
                counts.put(nums[i], count);
            }
            return -1;
        }

        /**
         * 3，位运算解决
         * 在java中int类型是32位的，我们只需要判断所有数字在某一位1的个数大于数组长度的一半，
         * 那么这个众数在这个位置肯定就是1，我们需要遍历32次，确定这个众数每个位置是0还是1即可。
         */
        public int majorityElement2(int[] nums) {
            int major = 0;
            int length = nums.length;
            //在java中int类型是32位，我们遍历每一位
            for (int i = 0, mask = 1; i < 32; i++, mask <<= 1) {
                //bitCounts表示所有数字在当前位置1的个数。比如当i=0
                //的时候，我们可以认为他表示的是所有数字在二进制位
                //中最右边1的总数。
                int bitCount = 0;
                for (int j = 0; j < length; j++) {
                    //判断数字nums[j]的第i（i从0开始）个位置是否为1，
                    //如果是1，bitCounts就加1
                    if ((nums[j] & mask) == 1) {
                        bitCount++;
                    }
                    //如果bitCounts大于数组的一半，那么这个众数在
                    //这个位置肯定是1，然后通过 major |= mask运算
                    //把这个位置变为1，后面不需要再判断了，直接终止
                    //内层循环
                    if (bitCount > length / 2) {
                        major |= mask;
                        break;
                    }
                }
            }
            return major;
        }

        /**
         * 4，摩尔投票法
         * 假设数组中每个不同的数字就代表一个国家，而数字的个数就代表这个国家的人数，他们在一起混战，
         * 就是每两个两个同归于尽。我们就可以知道那个人数大于数组长度一半的肯定会获胜。
         * <p>
         * 就算退一万步来说，其他的所有人都来攻击这个人数最多的国家，他们每两个两个同归于尽，最终剩下的也是那个众数。
         */
        public int majorityElement3(int[] nums) {
            int major = nums[0];
            int count = 1;
            for (int i = 1; i < nums.length; i++) {
                if (count == 0) {
                    //前面都消完了，在重新赋值
                    count++;
                    major = nums[i];
                } else if (major == nums[i]) {
                    //自己人，count就加1
                    count++;
                } else {
                    //不是自己人就同归于尽，消掉一个
                    count--;
                }
            }
            return major;
        }
    }
}
